package zgxt;

import java.util.Map;

public class Test3 {
    public static void main(String[] args) {

    }

    /**
     * 寻找最长的递增长度
     */
    int res = 0, row, col;
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int longestIncreasingPath (int[][] matrix) {
        this.row = matrix.length;
        if (row == 0) return 0;
        this.col = matrix[0].length;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dfs(i, j, 1, visited, matrix);
            }
        }
        return res;
    }

    public void dfs(int x, int y, int step, boolean[][] visited, int[][] matrix) {
        res = Math.max(res, step);
        visited[x][y] = true;
        int newX, newY;
        for (int[] d : direction) {
            newX = x + d[0];
            newY = y + d[1];
            if (valid(newX, newY) && !visited[newX][newY] && matrix[newX][newY] > matrix[x][y]) {
                dfs(newX, newY, step + 1, visited, matrix);
            }
        }
        visited[x][y] = false;
    }

    private boolean valid(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
}
